#include <stdio.h>
#include <stdlib.h>
struct TableNode
{
    double **Arr;
    int n;
    int m;
    int r;
    int c;
};
typedef struct TableNode *Matrix;
Matrix Make(Matrix T)
{
    T = malloc(sizeof(struct TableNode));
    if (T == NULL)
        printf("溢出");
    return T;
}
Matrix SetNM(Matrix T, int n, int m, int x)
{
    T->Arr = malloc(sizeof(double *) * (m + 2));
    for (int i = 0; i < m + 2; i++)
        T->Arr[i] = malloc(sizeof(double) * (n + 2 + x));
    T->n = n;
    T->m = m;
    T->r = m + 2;
    T->c = n + x + 2;
    for (int i = 0; i < T->r; i++)
        for (int j = 0; j < T->c; j++)
            T->Arr[i][j] = 0;
    return T;
}
void Print(Matrix T)
{
    printf("如下：\n");
    int i, j;
    for (i = 0; i < T->r; i++)
    {
        for (j = 0; j < T->c; j++)
            printf("%.2f\t", T->Arr[i][j]);
        printf("\n");
    }
}
void SetMatrix(Matrix T, int r, double *arr)
{
    int i, n;
    n = 0;
    for (i = 0; i < T->c; i++)
        T->Arr[r][i] = arr[n++];
}
void CountC_Z(Matrix T)
{
    for (int j = 1; j <= T->r; j++)
    {
        double t = T->Arr[0][j];
        for (int i = 1; i <= T->m; i++)
        {
            t -= T->Arr[0][(int)T->Arr[i][0]] * T->Arr[i][j];
        }
        T->Arr[T->r - 1][j] = t;
    }
}
void AnalyzeC_Z(Matrix T, int *A)
{
    double tmp = -1;
    A[0] = -2;
    for (int j = 1; j < T->c - 1; j++)
    {
        if (T->Arr[T->r - 1][j] > 0)
        {
            A[0] = -1;
            for (int i = 1; i <= T->m; i++)
            {
                if (T->Arr[i][j] > 0)
                {
                    A[0] = 0;
                }
            }
            if (A[0] == 0 && T->Arr[T->r - 1][j] > tmp)
            {
                A[1] = j;
                tmp = T->Arr[T->r - 1][j];
            }
        }
    }
    if (tmp == -1)
    {
        return;
    }
    tmp = -1;
    A[0] = 0;
    for (int i = 1; i <= T->m; i++)
    {
        if (T->Arr[i][A[1]] > 0)
        {
            if (T->Arr[i][A[1]] / T->Arr[i][T->c - 1] > tmp || T->Arr[i][T->c - 1] == 0)
            {
                A[0] = i;
                tmp = T->Arr[i][A[1]] / T->Arr[i][T->c - 1];
            }
        }
    }
    //printf("系数：%f，", tmp);
}
void Rotate(Matrix T, int *A)
{

    for (int i = 1; i <= T->m; i++)
    {
        if (i == A[0])
        {
            T->Arr[i][0] = A[1];
            double k = T->Arr[A[0]][A[1]];
            for (int j = 1; j < T->c; j++)
            {
                T->Arr[i][j] /= k;
            }
        }
        else if (T->Arr[i][A[1]] != 0)
        {
            double k = T->Arr[i][A[1]] / T->Arr[A[0]][A[1]];
            for (int j = 1; j < T->c; j++)
            {
                T->Arr[i][j] -= k * T->Arr[A[0]][j];
            }
        }
    }
    CountC_Z(T);
    //printf("换入变量:x[%d]", A[1]);
    CountZ(T);
    //printf("，Z=%f\n", T->Arr[T->r - 1][T->c - 1]);
}
void CountZ(Matrix T)
{
    double t = 0;
    for (int i = 1; i <= T->m; i++)
    {
        t += T->Arr[i][T->c - 1] * T->Arr[0][(int)T->Arr[i][0]];
    }
    T->Arr[T->r - 1][T->c - 1] = t;
}
void SolveTwo(Matrix T)
{
    CountC_Z(T);
    printf("原LP-");
    Print(T);
    int A[] = {0, 0};
    AnalyzeC_Z(T, A);
    while (A[0] != -1 && A[0] != -2)
    {
        Rotate(T, A);
        Print(T);
        AnalyzeC_Z(T, A);
    }
    if (A[0] == -2)
    {
        printf("结束-");
        CountZ(T);
        Print(T);
        return;
    }
    if (A[0] == -1)
    {
        printf("无解！");
        return;
    }
}
Matrix AnalyzeOne(Matrix T, double *tmp)
{
    printf("一阶段分析：\n");
    CountZ(T);
    if (T->Arr[T->r - 1][T->c - 1] != 0)
    {
        printf("原规划无解\n");
        return T;
    }
    for (int i = 1; i <= T->m; i++)
    {
        if (T->Arr[i][0] > T->n && T->Arr[i][0] < T->c - 1)
        {
            double t = T->Arr[i][0];
            T->Arr[i][0] = -1;
            for (int j = 1; j <= T->n; j++)
            {
                if (T->Arr[i][j] != 0)
                {
                    T->Arr[i][0] = t;
                    int a[] = {(int)i, (int)j};
                    printf("人工变量未出基:\n");
                    Rotate(T, a);
                    Print(T);
                    break;
                }
            }
        }
        if (T->Arr[i][0] == -1)
            T->m -= 1;
    }
    Matrix m = Make(NULL);
    SetNM(m, T->n, T->m, 0);
    for (int i = 0; i < m->c; i++)
        m->Arr[0][i] = tmp[i];
    for (int i = 1; i < m->r; i++)
    {
        if (T->Arr[i][0] == -1)
            continue;
        for (int j = 0; j < m->c; j++)
        {
            if (j == m->n + 1)
            {
                m->Arr[i][m->c - 1] = T->Arr[i][T->c - 1];
                break;
            }
            m->Arr[i][j] = T->Arr[i][j];
        }
    }
    return m;
}
Matrix SolveOne(Matrix T)
{
    double *tmp = malloc(sizeof(double) * T->c);
    for (int i = 0; i < T->c; i++)
    {
        tmp[i] = T->Arr[0][i];
        if (i > T->n && i < T->c - 1)
        {
            T->Arr[0][i] = -1;
        }
        else
        {
            T->Arr[0][i] = 0;
        }
    }
    SolveTwo(T);
    Matrix m = AnalyzeOne(T, tmp);
    return m;
}
int main()
{
    Matrix m = Make(NULL);
    // SetNM(m, 5, 3, 0);
    // double a0[] = {0, 2, 3, 0, 0, 0, 0};
    // SetMatrix(m, 0, a0);
    // double a1[] = {3, 1, 2, 1, 0, 0, 8};
    // SetMatrix(m, 1, a1);
    // double a2[] = {4, 4, 0, 0, 1, 0, 16};
    // SetMatrix(m, 2, a2);
    // double a3[] = {5, 0, 4, 0, 0, 1, 12};
    // SetMatrix(m, 3, a3);
    /* SetNM(m, 5, 3, 2);
    double a0[] = {0, 2, -1};
    SetMatrix(m, 0, a0);
    double a1[] = {6, 1, 1, -1, 0, 0, 1, 0, 2};
    SetMatrix(m, 1, a1);
    double a2[] = {7, 1, -1, 0, -1, 0, 0, 1, 1};
    SetMatrix(m, 2, a2);
    double a3[] = {5, 1, 0, 0, 0, 1, 0, 0, 3};
    SetMatrix(m, 3, a3); */
    // SetNM(m, 4, 4, 3);
    // double a0[] = {0, 3, 1, -2};
    // SetMatrix(m, 0, a0);
    // double a1[] = {5, 2, -1, 1, 0, 1, 0, 0, 4};
    // SetMatrix(m, 1, a1);
    // double a2[] = {6, 1, 1, 1, 0, 0, 1, 0, 6};
    // SetMatrix(m, 2, a2);
    // double a3[] = {4, 1, 0, 0, 1, 0, 0, 0, 2};
    // SetMatrix(m, 3, a3);
    // double a4[] = {7, 3, 0, 2, 0, 0, 0, 1, 10};
    // SetMatrix(m, 4, a4);
    // SetNM(m, 4, 3, 2);
    // double a0[] = {0, -1, 1};
    // SetMatrix(m, 0, a0);
    // double a1[] = {4, -1, 2, 1, 1, 0, 0, 2};
    // SetMatrix(m, 1, a1);
    // double a2[] = {5, -4, 4, -1, 0, 1, 0, 4};
    // SetMatrix(m, 2, a2);
    // double a3[] = {6, 1, 0, -1, 0, 0, 1, 0};
    // SetMatrix(m, 3, a3);
    // Matrix n = SolveOne(m);
    // SolveTwo(n);
    /* SetNM(m, 7, 5, 0);
    double a0[] = {0, 1, 4};
    SetMatrix(m, 0, a0);
    double a1[] = {3, 4, 5, 1, 0, 0, 0, 0, 20};
    SetMatrix(m, 1, a1);
    double a2[] = {4, -1, 1, 0, 1, 0, 0, 0, 1};
    SetMatrix(m, 2, a2);
    double a3[] = {5, 1, -2, 0, 0, 1, 0, 0, 1};
    SetMatrix(m, 3, a3);
    double a4[] = {6, 1, 0, 0, 0, 0, 1, 0, 3};
    SetMatrix(m, 4, a4);
    double a5[] = {7, 0, 1, 0, 0, 0, 0, 1, 2};
    SetMatrix(m, 5, a5); */
    // SetNM(m, 4, 2, 2);
    // double a0[] = {0, -2, -3, 5};
    // SetMatrix(m, 0, a0);
    // double a1[] = {5, 1, 1, 1, 0, 1, 0, 7};
    // SetMatrix(m, 1, a1);
    // double a2[] = {6, 2, -5, 1, -1, 0, 1, 10};
    // SetMatrix(m, 2, a2);
    //SolveTwo(m);
    /* SetNM(m, 6, 3, 0);
    double a0[] = {0, 4.5, 5, 4};
    SetMatrix(m, 0, a0);
    double a1[] = {4, 10, 5, 6, 1, 0, 0, 600};
    SetMatrix(m, 1, a1);
    double a2[] = {5, 6, 8, 9, 0, 1, 0, 600};
    SetMatrix(m, 2, a2);
    double a3[] = {6, 8, 10, 12, 0, 0, 1, 600};
    SetMatrix(m, 3, a3); */
    //Matrix n = Make(NULL);
    //n = SolveOne(m);
    /* SetNM(m, 5, 3, 0);
    double a0[] = {0, 1.2, 0.25};
    SetMatrix(m, 0, a0);
    double a1[] = {3, 2, 0.5, 1, 0, 0, 320};
    SetMatrix(m, 1, a1);
    double a2[] = {4, 4, -1, 0, 1, 0, 0};
    SetMatrix(m, 2, a2);
    double a3[] = {4, -6, 1, 0, 0, 1, 0};
    SetMatrix(m, 3, a3); */
    SetNM(m, 6, 3, 0);
    double a0[] = {0, 5, 4};
    SetMatrix(m, 0, a0);
    double a1[] = {4, 1, 2, 0, 1, 0, 0, 6};
    SetMatrix(m, 1, a1);
    double a2[] = {5, -1, 1, 0, 0, 1, 0, 1};
    SetMatrix(m, 2, a2);
    double a3[] = {6, 0, 1, 0, 0, 0, 1, 2};
    SetMatrix(m, 3, a3);
    SolveTwo(m);
    Print(m);
    return 0;
}
